"""
RouteGenerator.py
University: University of California, Los Angeles
Department: Center for Embedded Networked Sensing
Authors:    Victor Shia, Suming Chen, Vids Samanta 
Date:       2008-08-14 (Aug 14, 2008)

Summer@CENS 2008
"""

import sys, psycopg2, Queue, bisect, copy, httplib, urllib
import util, sampling
from decimal import *
import time, datetime, random
import getpass
import os, math
import PEIR, similar
from SOAPpy import WSDL
import json
import updateDB

nodeDict = {}
numberOfMisses = 0
weight   = Decimal("0.5")
debug    = True
inf      = float('inf')
similarityLimit = 0.05
speedDict = {'car' : 50, 'bike' : 16}
expandedNodes = []

username = ''
password = ''
dbname   = 'cyclesense'
host     = 'localhost'
modeOfT  = 'car'
sbuser   = ''
sbpw     = ''
location_json = {"gps_module_name":None,"latitude":None,
                 "longitude":None,"altitude":None,"horizontal_accuracy":None,
                 "vertical_accuracy":None,"fix_time":None,
                 "speed":None,"speed_accuracy":None,"heading":None,
                 "heading_accuracy":None,"horz_dilution_of_precision":None,
                 "vert_dilution_of_precision":None,"satellite_time_dilution_of_precision":None,
                 "satellite_time":None,
                 "satellites_in_view":None,"satellites_used":None}

def cost(road, modeOfT = 'car'):
    global weight
    voteThreshold = 5;
    
    totalCost = 0
    if modeOfT == 'car' and road[8] == 1:
        return Decimal('inf')
    if modeOfT == 'bike' and road[9] == 1: # unavailable
        return Decimal('inf')
#    if modeOfT == 'car' and road[11] == 1: # AND is only a bike route
#        return Decimal('inf')
    
    length  = road[3]
    
    temp = 1
    ranking = road[7]
    votes = road[10]
    
    if modeOfT == 'bike' and (road[11] == 1 or road[11] == 2 or road[11] == 3): # AND is a bike route
        #print road
        if votes < voteThreshold:
            if road[11] == 1:
                rankingToVote = 10
            elif road[11] == 2:
                rankingToVote = 8
            else:
                rankingToVote = 6
            modRanking = float(votes)/voteThreshold * ranking + (1 - float(votes)/voteThreshold)*rankingToVote
        else:
            modRanking = ranking
    elif modeOfT == 'bike':
        if votes < voteThreshold:
            modRanking = 4
        else:
            modRanking = ranking
    else:
        modRanking = 5

    temp = 5. / modRanking  #should change back to 5, me thinks
        
    totalCost = length * Decimal(str(temp)) * weight
    
    return totalCost

def heuristic(currentGPS, destNodeA, destNodeB):
    return Decimal(str((min(util.getApproxDistanceMiles(currentGPS, destNodeA), util.getApproxDistanceMiles(currentGPS, destNodeB)))))

def setConfig(user = '', pasw = '', dname = '', hostt = '', sbu = '', sbp = ''):
    global username, password, dbname, host, sbuser, sbpw
    a = os.path.exists('route/gpstrace.config')
    b = os.path.exists('gpstrace.config')
    if a or b:
        if a:
            f = open('route/gpstrace.config','r')
        else:
            f = open('gpstrace.config','r')
        
        for line in f:
            temp = line.split()
            if temp[0] == 'username':
                username = temp[2]
            elif temp[0] == 'password':
                password = temp[2]
            elif temp[0] == 'database':
                dbname = temp[2]
            elif temp[0] == 'host':
                host = temp[2]
            elif temp[0] == 'sbuser':
                sbuser = temp[2]
            elif temp[0] == 'sbpw':
                sbpw   = temp[2]
        f.close()

    if username == '':
        if user == '':
            username = raw_input("Username: ")
        else:
            username = user
    if password == '':
        if pasw == '':
            password = getpass.getpass()
        else:
            password = pasw
    if dbname == '':
        if dname == '':
            dbname = raw_input("Database: ")
        else:
            dbname = dname
    if host == '':
        if hostt == '':
            host = raw_input("Host: ")
        else:
            host = hostt
    if sbuser == '':
            sbuser = sbu
    if sbpw == '':
            sbpw = sbp

class potentialRoute:
    def __init__(self, route, nodes, cost, listOfCoords):
        self.routeSoFar  = route
        self.nodesTaken  = nodes
        self.totalCost   = cost
        self.nameOfRoads = []
        self.gpsCoords   = listOfCoords
     
    def appendToGPS(self, nextPair):
        if type(nextPair) is tuple:
            self.gpsCoords.append(nextPair)
        elif type(nextPair) is list:
            self.gpsCoords.extend(nextPair)
            
    def reverse(self):
        self.routeSoFar.reverse()
        self.nodesTaken.reverse()
        self.nameOfRoads.reverse()
        self.gpsCoords.reverse()

def getSpeedDict():
    return speedDict    

def changeWeight(num):
    global weight
    weight = Decimal(str(num))
    
def changeSimLmt(num):
    global similarityLimit
    similarityLimit = num

""" this function checks to see if anyone has inputted road ratings in sensorbase """
def checkSensorBase(cur, conn):
    global sbuser, sbpw
    if sbuser == '' or sbpw == '':
        return
    query = "SELECT counter FROM sensorbasecounter WHERE id = 1"
    cur.execute(query)
    results = cur.fetchall()
    index = results[0][0]
    #print index
    email = sbuser
    password = sbpw
    fields = "latitude,longitude,Rating2"
    tables = 'p_437_tags'
    condition = '1'
    wsdlFile = '/home/suming/sensorbase2.wsdl'
    "*** how many routes you want back***"
    delta = 5000
    format = 'csv'
    server = WSDL.Proxy(wsdlFile)
    #print "hey"
    #print email,password,fields,tables,condition,index,delta,format
    serverData = server.getData(email,password,fields,tables,condition,index,delta,format)
    if serverData == None:
        return 
    serverData = serverData.split('\n')
    serverData.pop(len(serverData) - 1)
    "*** this is used so we can write an insert statement incrementing the counter ***"
    counter = 0
    for sData in serverData:
        #print sData
        counter = counter + 1
        sData = sData.split(',')
        "*** bad user feedback..continue ***"
        rating = sData[2].strip('\'"[]')
        lat = sData[0]
        lon = sData[1]
        #print rating,lat,lon

        if util.isanum(rating) == 0 or util.isanum(lat) == 0 or util.isanum(lon) == 0 :
            continue
        ratingnum = eval(rating)
        if sData[0] == '' or sData [1] == '' or ratingnum < 1 or ratingnum > 10:
            continue
        #sData[3] = sData[3].strip('\'[]"')
        query = "SELECT gid,fnode,tnode,length,fename,fetype,ST_AsText(the_geom),ST_Distance(ST_GeomFromText('POINT (" + lon + " " + lat + ")',-1), the_geom) FROM la_roads WHERE ST_DWithin(ST_GeomFromText('POINT (" + lon + " "  + lat + ")',-1), the_geom, .001)"
        cur.execute(query)
        possibleEdges = cur.fetchall()
        "***find start edge with min distance***"
        closeEdge = []
        minSoFar = 9999999999999999
        for edge in possibleEdges:
            if edge[7] < minSoFar:
                minSoFar = edge[7]
                closeEdge = edge
        updateDB.markRouteRatingWithGID(edge[0], ratingnum)
    newvotes = index + counter
    query = "UPDATE sensorbasecounter SET counter = " + str(newvotes) + "WHERE id = 1"
    cur.execute(query)
    conn.commit()

""" this function uploads a routeList, s_addr, and e_addr to sensorbase
  routeList is in the format: lat, long, horz error, timestamp, speed, speed error

"""
def uploadToSensorbase(proj_id, table_name, routeList,s_addr,e_addr, sbuser, sbpw):
    global location_json
    if sbuser == '' or sbpw == '':
        return
    email    = sbuser
    password = sbpw    
    wsdlFile = '/home/suming/sensorbase2.wsdl'
    conn = httplib.HTTPConnection("sensorbase.org")

    xml_str = '<?xml version="1.0" encoding="UTF-8"?>'
    xml_str += '<table>'
    xml_str += '<row>'
    xml_str += '<field name="marker">Mark</field>'
    xml_str += '</row>'
    xml_str += '</table>'
    
    conn.request("POST", "/upload2.php", urllib.urlencode({
        'email':       email,
        'pw':           password,
        'data_string':  xml_str,
        'type':        'xml',
        'project_id':  proj_id,
        'tableName':   table_name
    }), {
        'Content-type': 'application/x-www-form-urlencoded',
        'Accept': 'text/plain'
    })
    response = conn.getresponse()
    responseText = response.read()

    if responseText != 'Data successfully slogged!\n':
        return (1, responseText)

    xml_str = '<?xml version="1.0" encoding="UTF-8"?>'
    xml_str += '<table>'
    xml_str += '<row>'
    xml_str += '<field name="start_address">' + s_addr + '</field>'
    xml_str += '<field name="end_address">' + e_addr + '</field>'
    xml_str += '</row>'
    xml_str += '</table>'
    
    conn.request("POST", "/upload2.php", urllib.urlencode({
        'email':       email,
        'pw':           password,
        'data_string':  xml_str,
        'type':        'xml',
        'project_id':  proj_id,
        'tableName':   table_name
    }), {
        'Content-type': 'application/x-www-form-urlencoded',
        'Accept': 'text/plain'
    })
    response = conn.getresponse()
    responseText = response.read()

    def makeLocationJson(route):    
        loc_json = location_json.copy()
        loc_json['latitude']  = route[0]
        loc_json['longitude'] = route[1]
        loc_json['horizontal_accuracy'] = route[2] 
        loc_json['speed']     = route[4]
        loc_json['speed_accuracy'] = route[5]
        return loc_json
        
    for route in routeList:
        xml_str = '<?xml version="1.0" encoding="UTF-8"?>'
        xml_str += '<table>'
        xml_str += '<row>'
        xml_str += '<field name="location_json">' + json.write(makeLocationJson(route)) + '</field>'
        xml_str += '<field name="Timestamp">' + str(route[3]) + '</field>'
        xml_str += '</row>'
        xml_str += '</table>'
        
        conn.request("POST", "/upload2.php", urllib.urlencode({
            'email':       email,
            'pw':           password,
            'data_string':  xml_str,
            'type':        'xml',
            'project_id':  proj_id,
            'tableName':   table_name
        }), {
            'Content-type': 'application/x-www-form-urlencoded',
            'Accept': 'text/plain'
        })
        response = conn.getresponse()
        responseText = response.read()

    conn.close()

    return (0, 'Successfully uploaded')

"""
 this function looks in the cache for the node_num or queries the database
 Arguments: node number, and cur = cursor to database
 Returns: a list of queries
"""

def getPossibleRoads(node_num, cur):
    global nodeDict, numberOfMisses, nFile, expandedNodes
    if numberOfMisses == 0:
        expandedNodes = []
    
    if node_num not in nodeDict:
        numberOfMisses += 1
        query = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom),ranking,unavailableCars,unavailableBikes,votes,bikeclass FROM la_roads WHERE fnode =" + str(node_num) + " OR tnode =" + str(node_num)
        cur.execute(query)
        possibleRoads = cur.fetchall()
        nodeDict[node_num] = possibleRoads       
    
    if debug:
        if node_num not in expandedNodes:
            testEdge = nodeDict[node_num][0]
            if testEdge[1] == node_num:
                nFile.write(str(util.parseGeoText(testEdge[6])[0]).strip('()') + '\n')
            elif testEdge[2] == node_num:
                nFile.write(str(util.parseGeoText(testEdge[6])[-1]).strip('()') + '\n')
            expandedNodes.append(node_num)
        
    return nodeDict[node_num]

""" this method updates the ranking in the cache """
def updateRanking(node_num1, node_num2, ranking):
    global nodeDict
    if node_num1 in nodeDict:
        possibleRoads1 = nodeDict[node_num1]
        newPossibleRoads1 = possibleRoads1[:]
        
        counter = 0
        for possibleRoad in possibleRoads1:
            if possibleRoad[1] == node_num2 or possibleRoad[2] == node_num2:
                templist = list(newPossibleRoads1[counter])
                templist[7] = ranking
                templist[10] += 1
                temptuple = tuple(templist)
                newPossibleRoads1[counter] = temptuple
            counter = counter + 1
        nodeDict[node_num1] = newPossibleRoads1
        #print nodeDict[node_num1]
        
    if node_num2 in nodeDict:
        possibleRoads2 = nodeDict[node_num2]
        newPossibleRoads2 = possibleRoads2[:]
        counter = 0
        for possibleRoad in possibleRoads2:
            #possibleRoad = list(possibleRoad)
            if possibleRoad[1] == node_num2 or possibleRoad[2] == node_num2:
                templist = list(newPossibleRoads2[counter])
                templist[7] = ranking
                templist[10] += 1
                temptuple = tuple(templist)
                newPossibleRoads2[counter] = temptuple
            counter = counter + 1
        nodeDict[node_num2] = newPossibleRoads2
        #print nodeDict[node_num2]

"""
 unavailable is 1 if it is unavailable, 0 if it is available
 forCars is true if this is a car
 forCars is false if this is a bike
"""
def updateUnavailability(node_num1, node_num2, unavailable, forCars):
    global nodeDict
    
    if node_num1 in nodeDict:
        possibleRoads1 = nodeDict[node_num1]
        newPossibleRoads1 = possibleRoads1[:]
        
        counter = 0
        for possibleRoad in possibleRoads1:
            if possibleRoad[1] == node_num2 or possibleRoad[2] == node_num2:
                templist = list(newPossibleRoads1[counter])
                if forCars:
                    templist[8] = unavailable
                else:
                    templist[9] = unavailable
                temptuple = tuple(templist)
                newPossibleRoads1[counter] = temptuple
            counter = counter + 1
        nodeDict[node_num1] = newPossibleRoads1
        #print nodeDict[node_num1]
        
    if node_num2 in nodeDict:
        possibleRoads2 = nodeDict[node_num2]
        newPossibleRoads2 = possibleRoads2[:]
        counter = 0
        for possibleRoad in possibleRoads2:
            if possibleRoad[1] == node_num2 or possibleRoad[2] == node_num2:
                templist = list(newPossibleRoads2[counter])
                if forCars:
                    templist[8] = unavailable
                else:
                    templist[9] = unavailable
                temptuple = tuple(templist)
                newPossibleRoads2[counter] = temptuple
            
            counter = counter + 1
        nodeDict[node_num2] = newPossibleRoads2
        #print nodeDict[node_num2]

"""
 Arguments: num, num, num, num, num, str
 numRoutes = number of routes desired
 modeOfT = 'bike' or 'car'
 Outputs: ( status, route )
 Status of 0 indicates success
"""
def generateRouteFromGPS(startLat, startLon, endLat, endLon, numRoutes, modeOfT):    
    global username, password, host, dbname
    conn = psycopg2.connect("dbname = '" + dbname + "' host = '" + host + "' user = " + username + " password = " + password)
    cur = conn.cursor()
    startQuery = "SELECT gid,fnode,tnode,length,fename,fetype,ST_AsText(the_geom),ST_Distance(ST_GeomFromText('POINT (" + str(startLon) + " " + str(startLat) + ")',-1), the_geom) FROM la_roads WHERE ST_DWithin(ST_GeomFromText('POINT (" + str(startLon) + " " + str(startLat) + ")',-1), the_geom, .001)"
    cur.execute(startQuery)
    "*** there should be more than 1 edge fetched...***"
    startEdges = cur.fetchall()
    destQuery = "SELECT gid,fnode,tnode,length,fename,fetype,ST_AsText(the_geom),ST_Distance(ST_GeomFromText('POINT (" + str(endLon) + " " + str(endLat) + ")',-1), the_geom) FROM la_roads WHERE ST_DWithin(ST_GeomFromText('POINT (" + str(endLon) + " "  + str(endLat) + ")',-1), the_geom, .001)"
    cur.execute(destQuery)
    destEdges = cur.fetchall()
    "***find start edge with min distance***"
    startEdge = []
    startMinSoFar = 9999999999999999
    for edge in startEdges:
        if edge[7] < startMinSoFar:
            startMinSoFar = edge[7]
            startEdge = edge
    "*** find dest edge with min distance***"
    destEdge = []
    destMinSoFar = 9999999999999999
    for edge in destEdges:
        if edge[7] < destMinSoFar:
            destMinSoFar = edge[7]
            destEdge = edge
    
    a = pinPointGPSFromGPS((startLat, startLon), [startEdge], True)
    b = pinPointGPSFromGPS((endLat, endLon), [destEdge], False)
    half = int((numRoutes + 0.5) / 2)

    list2 = generateRoute([destEdge], b, [startEdge], a, cur, numRoutes - half, modeOfT, conn, [])
    for list in list2:
        list.reverse()
    list1 = generateRoute([startEdge], a, [destEdge], b, cur, numRoutes, modeOfT, conn, list2)
    return [0, list1]

""" this pinpoints the GPS coordinates of the start and creates the route from
    the edge to the actual GPS point
    gpsCoord is a tuple of lat, long
    node is an object of potentialRoute
    beginning is True is it is the start edge, False if it is the end edge.
    outputs:  (route to the node and length, route to other node and length)
"""
def pinPointGPSFromGPS(gpsCoord, node, beginning):
    gpsCoord     = (gpsCoord[0], gpsCoord[1])
    startNode    = node[0]
    gps          = util.parseGeoText(startNode[6])
    edgesInRoad  = len(gps) - 1
    length       = []
    totalLen     = 0
    gpsListToF   = []
    gpsListToT   = []
    distToSides  = []
    lenToF       = 0
    for edgeNum in range(edgesInRoad):
        length.append(float(util.getApproxDistanceMiles(gps[edgeNum], gps[edgeNum + 1])))
        totalLen += length[edgeNum]
        distToSides.append((float(util.getApproxDistanceMiles(gpsCoord, gps[edgeNum]))      , 
                            float(util.getApproxDistanceMiles(gpsCoord, gps[edgeNum + 1]))))
    minL  = [100,100]  # [ node number , distance to Node]
    minR  = [100,100] 
    for x in range(len(distToSides)):
        if minL[1] > distToSides[x][0]:
            minL = [x, distToSides[x][0]]
        if minR[1] > distToSides[x][1]:
            minR = [x + 1, distToSides[x][1]]

    if minL[0] is not minR[0] - 1:
        "PRINT YOU'RE IN TROUBLEEE"
        
    edgeNum = minL[0]
    for x in range(edgeNum):
        gpsListToF.append(gps[x])
        lenToF += length[x]
    for x in range(edgeNum + 1,edgesInRoad):
        gpsListToT.append(gps[x])
    
    gpsListToF.append(gpsCoord)
    gpsListToT.reverse()
    gpsListToT.append(gpsCoord)
    
    lenToF = Decimal(str(lenToF))
    totalLen = Decimal(str(totalLen))
    
    if beginning:
        gpsListToF.reverse()
        gpsListToT.reverse()
        return [(gpsListToF, lenToF), (gpsListToT, totalLen - lenToF)]
    else:
        return [(gpsListToF, lenToF), (gpsListToT, totalLen - lenToF)]

"""
 inputs:
     status 0 indicates success
     status 1 indicates too many start roads
     status 2 indicates too many dest roads
     sAddress is start in form [house number] [ address ] [Rd., Blvd., ...] , [zipcode]
     dAddress is end
     numRoutes is the number of routes wanted.
     modeOfT is 'car' or 'bike'
  outputs: (status, list of potentialRoutes)
"""
def generateRouteFromAddress(sAddress, dAddress, numRoutes, modeOfT):    
    global username, password, host, dbname
    try:
        startAddress, startStreetName, startRoadType, startZip = util.splitAddress(sAddress)
        destAddress, destStreetName, destRoadType, destZip = util.splitAddress(dAddress)
    except Exception:
        return []
    #destination = util.splitAddress(dAddress)
    
    conn = psycopg2.connect("dbname = '" + dbname + "' host = '" + host + "' user = " + username + " password = " + password)
    cur = conn.cursor()
    
    startLOR = ['fraddl', 'toaddl']
    if startAddress != '' and eval(startAddress) % 2 == 1:
        startLOR = ['fraddr', 'toaddr']

    destLOR = ['fraddl', 'toaddl']
    if destAddress != '' and eval(destAddress) % 2 == 1:
        destLOR = ['fraddr', 'toaddr']
    
    if startAddress == '':
        startQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), fraddl, toaddl FROM la_roads WHERE fename = '" + startStreetName + "' AND fetype = '" + startRoadType + "' AND (zipl = '" + startZip + "' OR zipr = '" + startZip + "')"
        cur.execute(startQuery)
        startEdge = cur.fetchall()
    else:
        startQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), " + startLOR[0] + " , " + startLOR[1] + " FROM la_roads WHERE fename = '" + startStreetName + "' AND fetype = '" + startRoadType + "' AND (" + startAddress + " BETWEEN " + startLOR[0] + " AND " + startLOR[1] + ") AND (zipl = '" + startZip + "' OR zipr = '" + startZip + "')"
    cur.execute(startQuery)
    startEdge = cur.fetchall()

    if destAddress == '':
        destQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), fraddl, toaddl FROM la_roads WHERE fename = '" + destStreetName + "' AND fetype = '" + destRoadType + "' AND (zipl = '" + destZip + "' OR zipr = '" + destZip + "')"
    else:
        destQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), " + destLOR[0] + " , " + destLOR[1] + " FROM la_roads WHERE fename = '" +     destStreetName + "' AND fetype = '" + destRoadType + "' AND (" + destAddress + " BETWEEN " + destLOR[0] + " AND " + destLOR[1] + ") AND (zipl = '" + destZip + "' OR zipr = '" + destZip + "')"
    cur.execute(destQuery)
    destEdge = cur.fetchall()
    
    if len(startEdge) != 1:
        print "CAN'T FIND A SPECIFIC START ADDRESS"
        startQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), fraddl, toaddl, fraddr, toaddr FROM la_roads WHERE fename = '" + startStreetName + "' AND fetype = '" + startRoadType + "' AND (zipl = '" + startZip + "' OR zipr = '" + startZip + "')"
        cur.execute(startQuery)
        startEdge = cur.fetchall()
        return [1, startEdge]
    if len(destEdge) != 1:
        print "CAN'T FIND A SPECIFIC DESTINATION ADDRESS"
        destQuery = "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), fraddl, toaddl, fraddr, toaddr FROM la_roads WHERE fename = '" + destStreetName + "' AND fetype = '" + destRoadType + "' AND (zipl = '" + destZip + "' OR zipr = '" + destZip + "')"
        cur.execute(destQuery)
        destEdge = cur.fetchall()
        return [2, destEdge]
    
    if len(startEdge) == 0:
        return []
    elif len(destEdge) == 0:
        return []
    elif len(startEdge) > 1 and len(destEdge) > 1:
        return []
    #elif len(startEdge) > 1:
    #    print "THERE ARE MULTIPLE START ADDRESSES"
    #    return generateRoute(startEdge, [([],0),([],0)], destEdge, pinPointGPSFromAddress(destAddress, destEdge, False), cur, numRoutes, modeOfT, conn)
    #elif len(destEdge) > 1:
    #    print "THERE ARE MULTIPLE DEST ADDRESSES"
    #    return generateRoute(startEdge, pinPointGPSFromAddress(startAddress, startEdge, True), destEdge, [([],0),([],0)], cur, numRoutes, modeOfT, conn)
    
    a = pinPointGPSFromAddress(startAddress, startEdge, True)
    b = pinPointGPSFromAddress(destAddress, destEdge, False)
    half = int((numRoutes + 0.5) / 2)

    list2 = generateRoute(destEdge, b, startEdge, a, cur, numRoutes - half, modeOfT, conn, [])
    for list in list2:
        list.reverse()
        
    list1 = generateRoute(startEdge, a, destEdge, b, cur, numRoutes , modeOfT, conn, list2)
    return [0, list1]

""" this pinpoints the GPS coordinates of the start and creates the route from
    the edge to the actual GPS point
    addressNum is the house number of the thing
    node is an object of potentialRoute
    beginning is True is it is the start edge, False if it is the end edge.
    outputs:  (route to the node and length, route to other node and length)
"""
def pinPointGPSFromAddress(addressNum, node, beginning):
    if type(addressNum) is str:
        addressNum = eval(addressNum)
    
    startNode    = node[0]
    gps          = util.parseGeoText(startNode[6])
    s_fnode      = startNode[7]
    s_tnode      = startNode[8]
    percentFromF = float(( Decimal(str(addressNum)) - s_fnode) / ( s_tnode - s_fnode))
    edgesInRoad  = len(gps) - 1
    length       = []
    totalLen     = 0
    gpsListToF   = []
    gpsListToT   = []
    
    for edgeNum in range(edgesInRoad):
        length.append(float(util.getApproxDistanceMiles(gps[edgeNum], gps[edgeNum + 1])))
        totalLen += length[edgeNum]

    # TO FNODE
    edgeNum = 0
    tempLen = 0
    while (tempLen + length[edgeNum] / totalLen) < percentFromF:
        if edgeNum == edgesInRoad - 1:
            break;
        edgeNum += 1
        tempLen += length[edgeNum]
        gpsListToF.append(gps[edgeNum])
    
    # TO TNODE
    for x in range(edgeNum + 1,edgesInRoad):
        gpsListToT.append(gps[x])
        
    percentFromEdge = (totalLen * 1.0 * percentFromF - tempLen) / length[edgeNum]
    
    startGPS = []
    for x in range(len(gps[edgeNum])):
        startGPS.append(gps[edgeNum][x] + percentFromEdge * (gps[edgeNum + 1][x] - gps[edgeNum][x]))
    startGPS = tuple(startGPS)
    
    gpsListToF.append(startGPS)
    gpsListToT.reverse()
    gpsListToT.append(startGPS)
    
    tempLen = Decimal(str(totalLen * percentFromF))
    totalLen = Decimal(str(totalLen))
    
    if beginning:
        gpsListToF.reverse()
        gpsListToT.reverse()
        return [(gpsListToF, tempLen), (gpsListToT, totalLen - tempLen)]
    else:
        return [(gpsListToF, tempLen), (gpsListToT, totalLen - tempLen)]
    
"""
 MAIN ENGINE OF A-STAR
 START EDGE AND DEST EDGE ARE DEFINED BY THE QUERY: "SELECT gid,fnode,tnode,length,fename,fetype, ST_AsText(the_geom), fraddl, toaddl FROM la_roads WHERE ..."
 routeToStartEdge/routeToDestEdge are the routes of pinPointGPSFrom_____
 numRoutes is the number of routes desired
"""
def generateRoute(startEdge, routeToStartEdge, destEdge, routeToDestEdge, cur, numRoutes, modeOfT, conn, results = []): 
    if numRoutes == 0:
        return []
    
    "***two startNodes and two destNodes**"
    checkSensorBase(cur, conn)
    startNodeA       = startEdge[0][1]
    startNodeB       = startEdge[0][2]
    startRoadSegment = startEdge[0][0]
    temp             = util.parseGeoText(startEdge[0][6])
    gpsStartNodeA    = temp[0]
    gpsStartNodeB    = temp[-1] 
    destNodeA        = destEdge[0][1]
    destNodeB        = destEdge[0][2]
    temp             = util.parseGeoText(destEdge[0][6])
    gpsDestNodeA     = temp[0]
    gpsDestNodeB     = temp[-1] 
    

    "*** put in the starting two points***"
    routeA = routeToStartEdge[0][0]
    routeA.append(gpsStartNodeA)
    routeB = routeToStartEdge[1][0]
    routeB.append(gpsStartNodeB)
    x1 = potentialRoute([startRoadSegment], [startNodeA], routeToStartEdge[0][1], routeA)
    x2 = potentialRoute([startRoadSegment], [startNodeB], routeToStartEdge[1][1], routeB)

    fringe = util.PriorityQueue()
    fringe.push(x1,x1.totalCost + heuristic(gpsStartNodeA, gpsDestNodeA, gpsDestNodeB))
    fringe.push(x2,x2.totalCost + heuristic(gpsStartNodeB, gpsDestNodeA, gpsDestNodeB))
    
    resultsFound = len(results)
    count = 0
    while resultsFound < numRoutes and not fringe.isEmpty():
        count += 1
        nodeX = fringe.pop()
        if count % 100 == 0:
            print "count",count
        #print nodeX.routeSoFar[-1]
        lastNodeTaken = nodeX.nodesTaken[-1]
        if (lastNodeTaken == destNodeA or lastNodeTaken == destNodeB):
            save = True
            for route in results:
                t = similar.similarityFunction(route.gpsCoords, nodeX.gpsCoords)
                print t
                if t < similarityLimit:
                    save = False
            print nodeX.totalCost
            if save == True:
                #print str(nodeX.totalCost)
                if lastNodeTaken == destNodeA:
                    nodeX.appendToGPS(routeToDestEdge[0][0])
                    nodeX.totalCost += routeToDestEdge[0][1]
                else:
                    nodeX.appendToGPS(routeToDestEdge[1][0])
                    nodeX.totalCost += routeToDestEdge[1][1]
                resultsFound = resultsFound + 1
                results.append(nodeX)
        else:
            possibleRoads = getPossibleRoads(lastNodeTaken, cur)
            for road in possibleRoads:
                if (road[0] in nodeX.routeSoFar):
                    continue
                else:
                    nodeY = copy.deepcopy(nodeX)
                    nodeY.routeSoFar.append(road[0])
                    temp = util.parseGeoText(road[6])
                    if road[1] == lastNodeTaken:
                        nodeY.nodesTaken.append(road[2])
                        tempGPS = temp[-1]
                    else:
                        nodeY.nodesTaken.append(road[1])
                        tempGPS = temp[0]
                    nodeY.appendToGPS(tempGPS)
                    nodeY.totalCost += cost(road, modeOfT) #road[3]  add on the cost
                    nodeY.nameOfRoads.append(road[4])
                    fringe.push(nodeY, nodeY.totalCost + heuristic(tempGPS, gpsDestNodeA, gpsDestNodeB))

    """
    #for result in routes:
        #print result.nameOfRoads
        #print result.nodesTaken
        #print result.routeSoFar
        #print result.nameOfRoads
        print result.gpsCoords
    #print "count = ", str(count)
    """
    return results


# ========================================================================================== #
# Interfaces for outside methods
# ========================================================================================== #

""" get Road names"""
def getRoadNames(queryList):
    names = []
    for query in queryList:
        t = []
        if query[7] != 0 and query[8] != 0:
            t.append(str(query[7]) + " to " + str(query[8]))
        if query[9] != 0 and query[10] != 0:
            t.append(str(query[9]) + " to " + str(query[10]))
        t.append(query[4])
        t.append(query[5])
        names.append(t)
    return names

"""
 GENERATE ROUTE TO FILE
 output: files
 gpsTrace_#_.txt and gpsTraceNoisy_#_.txt
 text files are in the following format:
 lat, long, horizontal accuracy, timestamp, speed, speed accuracy
"""
def generateRoutesToFile(numRoutes, sAddress, dAddress, start = datetime.datetime.now(), modeOfT = 'car', interval = 10, speed = 0):
    global username, password, dbname, host, speedDict, nFile, debug

    if debug:
        nFile    = open('latlongs.txt', 'w')
    
    if username == '' or password == '' or dbname == '' or host == '':
        setConfig()
    
    startTime = time.time()
    routes = generateRouteFromAddress(sAddress, dAddress, numRoutes, modeOfT)
    
    if routes[0] != 0:
        print "ERROR"
        if routes[0] == 1:
            print "Bad starting address"
        if routes[0] == 2:
            print "Bad destination address"            
        print "Possible road addresses"
        print getRoadNames(routes[1])
        exit()
    else:
        routes.pop(0)
        routes = routes[0]
    
    print "DONE GENERATING"
    
    if speed == 0:
        speed = speedDict[modeOfT]
        
    base      = "gpsTrace"
    num      = 0
    for result in routes:
        temp = sampling.getCoordinatesBetweenXandY(result.gpsCoords, speed, interval, start)        
        f = open(base + str(num) + '.txt', 'w')
        for lat,lon,horzAcc,tim,speed,speedAcc in temp[0]:
            f.write(str(lat))
            f.write(",")
            f.write(str(lon))
            f.write(",")
            f.write(str(horzAcc))
            f.write(",")
            f.write(str(tim))
            f.write(",")
            f.write(str(speed))
            f.write(",")
            f.write(str(speedAcc))
            f.write("\n")
        f.close()
        
        f = open(base + "Noisy" + str(num) + '.txt', 'w')
        for lat,lon,horzAcc,tim,speed,speedAcc in temp[1]:
            f.write(str(lat))
            f.write(",")
            f.write(str(lon))
            f.write(",")
            f.write(str(horzAcc))
            f.write(",")
            f.write(str(tim))
            f.write(",")
            f.write(str(speed))
            f.write(",")
            f.write(str(speedAcc))
            f.write("\n")
        f.close()
        num = num + 1
        
    totalTime = time.time() - startTime
    if debug:
        nFile.close()
    
    print 'process took',totalTime,'to complete'

"""
 GENERATE ROUTE TO DJANGO
 USED FOR THE WEB INTERFACE
 
 output:
   (list of routes where routes is a list of gps coordinates, processing time)
"""
def generateRoutesToDjango(numRoutes, sAddress, dAddress, start = datetime.datetime.now(), modeOfT = 'bike', interval = 10, speed = 0, noise = True):
    global nodeDict, numberOfMisses, speedDict, nFile, debug
    
    if debug:
        nFile    = open('latlongs.txt', 'w')
    #nodeDict = {}
    numberOfMisses = 0
    startTime = time.time()
    routes = generateRouteFromAddress(sAddress, dAddress, numRoutes, modeOfT)
    
    if len(routes) == 0:
        return []
    if routes[0] != 0:
        return [routes[0], getRoadNames(routes[1]), 0]
    else:
        routes.pop(0)
        routes = routes[0]
        
    if speed == 0:
        speed = speedDict[modeOfT]

    rtnCoord = []
    for result in routes:
        if noise:
            rtnCoord.append(sampling.getCoordinatesBetweenXandY(result.gpsCoords, speed, interval,start)[1])
        else:
            rtnCoord.append(sampling.getCoordinatesBetweenXandY(result.gpsCoords, speed, interval,start)[0])
    totalTime = time.time() - startTime
    
    print "number of misses", numberOfMisses
    
    if debug:
        nFile.close()

    return [0, rtnCoord, totalTime]

# ========================================================================================== #
# END
# ========================================================================================== #

if __name__ == "__main__":
    if len(sys.argv) >= 2:
        # numRoutes, sAddress, dAddress, start = datetime.datetime.now(), modeOfT = 'car', interval = 10, speed = 0
        # python RouteGenerator.py -a [numRoutes] [address1] [address2]
        if sys.argv[1] == '-a':
            if len(sys.argv) == 5:
                generateRoutesToFile(eval(sys.argv[2]), sys.argv[3], sys.argv[4])
            elif len(sys.argv) == 6:
                generateRoutesToFile(eval(sys.argv[2]), sys.argv[3], sys.argv[4], modeOfT = sys.argv[5])
            elif len(sys.argv) == 7:
                generateRoutesToFile(eval(sys.argv[2]), sys.argv[3], sys.argv[4], modeOfT = sys.argv[5], interval = eval(sys.argv[6]))
            elif len(sys.argv) == 8:
                generateRoutesToFile(eval(sys.argv[2]), sys.argv[3], sys.argv[4], modeOfT = sys.argv[5], interval = eval(sys.argv[6]), speed = eval(sys.argv[7]))
            else:
                print "BAD FORMAT \n"
                print "FORMAT: -a [num Routes] [start address] [end address] "
                print "FORMAT: -a [num Routes] [start address] [end address] ['bike' or 'car']"
                print "FORMAT: -a [num Routes] [start address] [end address] ['bike' or 'car'] [sampling interval in seconds]"
                print "FORMAT: -a [num Routes] [start address] [end address] ['bike' or 'car'] [sampling interval in seconds] [speed in km/h]"
        elif sys.argv[1] == '-g':
            #numRoutes, startLat, startLong, endLat, endLong, speed = 0, sampleRate = 10, start = datetime.datetime.now(), modeOfT = 'car'
            if len(sys.argv) == 10:
                PEIR.peir_interface(eval(sys.argv[2]), eval(sys.argv[3]), eval(sys.argv[4]), eval(sys.argv[5]), eval(sys.argv[6]), modeOfT = sys.argv[7], sampleRate = eval(sys.argv[8]), speed = eval(sys.argv[9]))
            elif len(sys.argv) == 9:
                PEIR.peir_interface(eval(sys.argv[2]), eval(sys.argv[3]), eval(sys.argv[4]), eval(sys.argv[5]), eval(sys.argv[6]), modeOfT = sys.argv[7], sampleRate = eval(sys.argv[8]))
            elif len(sys.argv) == 8:
                PEIR.peir_interface(eval(sys.argv[2]), eval(sys.argv[3]), eval(sys.argv[4]), eval(sys.argv[5]), eval(sys.argv[6]), modeOfT = sys.argv[7])
            elif len(sys.argv) == 7:
                PEIR.peir_interface(eval(sys.argv[2]), eval(sys.argv[3]), eval(sys.argv[4]), eval(sys.argv[5]), eval(sys.argv[6]))
            else:
                print "BAD FORMAT \n"
                print "FORMAT: -g [number of paths] [start lat] [start long] [end lat] [end long] ['bike or car'] [ sample rate] [ speed ]OR \n"
                print "FORMAT: -g [number of paths] [start lat] [start long] [end lat] [end long] ['bike or car'] [ sample rate] OR \n"
                print "FORMAT: -g [number of paths] [start lat] [start long] [end lat] [end long] ['bike or car'] OR \n"
                print "FORMAT: -g [number of paths] [start lat] [start long] [end lat] [end long]"
        else:
            print "BAD FORMAT \n"
            print "options: \n"
            print "-a : address \n"
            print "-g : gps \n"
    else:
        print "INCORRECT FORMAT"
        print "BAD FORMAT \n"
        print "options: \n"
        print "-a : address \n"
        print "-g : gps \n"